<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>radixSort</title>
</head>

<body>
    <script>
        function radixSort(arr, maxDigit) { //LSD
            var counter = [];
            var mod = 10;
            var dev = 1;
            for (var i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {
                for (var j = 0; j < arr.length; j++) {
                    var bucket = parseInt((arr[j] % mod) / dev);
                    console.log(bucket)
                    if (counter[bucket] == null) {
                        counter[bucket] = [];
                    }
                    counter[bucket].push(arr[j]);
                }
                var pos = 0;
                for (var j = 0; j < counter.length; j++) {
                    var value = null;
                    if (counter[j] != null) {
                        while ((value = counter[j].shift()) != null) {
                            arr[pos++] = value;
                        }
                    }
                }
            }
            return arr;
        }
        //MSD
        var post = 0
        //实现不了啊，arr第二次递归编程tempArr了，改变的是temp的，不是最外层的arr
        //只能把arr绑在全局上，改变全局的值
        function radixMSDSort(arr, maxDigit) {
            //console.log("before:" + arr)
            let counter = []
            let dev = Math.pow(10, maxDigit - 1)
            for (let i = 0; i < arr.length; i++) {
                let bucket = parseInt((arr[i] / dev) % 10)
                if (counter[bucket] == null) {
                    counter[bucket] = []
                }
                counter[bucket].push(arr[i])
            }
            //console.log(counter)
            for (let j = 0; j < counter.length; j++) {
                if (counter[j] != null && counter[j].length > 1) { //如果桶中的数大于1
                    let tempArr = new Array(counter[j].length)
                    for (let a = 0; a < counter[j].length; a++) {
                        tempArr[a] = counter[j][a]
                    }
                    //console.log(tempArr)
                    radixMSDSort(tempArr, Math.max(...tempArr).toString().length)


                } else if (counter[j] != null) { //桶中的数为1 直接取出
                    //console.log("j:" + j + " " + counter[j])
                    //arr[post++] = counter[j][0]
                    window.arr[post++] = counter[j][0]
                }
            }
            //console.log("after:" + arr)
            return arr
        }
        var arr = [9, 55, 8, 1, 12, 3]
        console.log(radixMSDSort(arr, 2))
        //console.log(window.arr)
    </script>
</body>

</html>